import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class Sort {

    //从小到大排序
    //自己写的版本写成还是写成交换了
    public static void insertSort1(int[] arr){
        int j = 0;
        int k = 0;
        for (int i = 1; i < arr.length; i++) {
            j = i - 1;
            k = i;
            while(j >= 0){
                if(arr[j] > arr[k]){
                    int temp = arr[k];
                    arr[k] = arr[j];
                    arr[j] = temp;
                    k--;
                    j--;
                }else{
                    break;
                }
            }
        }
    }

    //直接插入排序：
    //修改之后的版本：
    //时间复杂度 O(N²)
    //最好情况的时间复杂度 O(N)，不用排序，只判断一次，当数据趋于有序的时候，这种排序的速度越来越快
    //空间复杂度 O(1)
    public static void insertSort(int[] arr){

        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int j = i - 1;
            for (; j >= 0 ; j--) {
                //这里不加等号的话，插入排序就是稳定的
                //如果一个排序是稳定的，那么可以实现成不稳定的
                //如果一个排序本身是不稳定的，那么不能把它变成稳定的
                if(arr[j] > temp){
                    arr[j+1] = arr[j];
                }else{
                    break;
                }
            }
            arr[j+1] = temp;
        }
    }
    
    //希尔排序：插入排序的优化
    public static void shellSort(int[] arr){
        int gap = arr.length;
        while(gap > 1){
            gap /= 2;
            shell(arr,gap);
        }
    }

    //希尔排序里面的循环还可以写成下面的形式
    //这种写法，比较清楚的说明，不管前几次分组排序排得怎么样，最后还得以间隔为1插入排序
    public static void shellSort1(int[] arr){
        int gap = arr.length;
        while(gap > 1){
            shell(arr,gap);
            gap /= 2;
        }
        shell(arr,1);
    }
    
    private static void shell(int[] arr,int gap){
        //分成两组时，i++的话就是两组轮流插入排序，而不是先一组插入排序完成之后再去插入排序第二组
        for (int i = gap; i < arr.length; i++) {
            int temp = arr[i];
            int j = i - gap;
            for (; j >= 0; j -= gap) {
                if(arr[j] > temp){
                    arr[j + gap] = arr[j];
                }else{
                    break;
                }
            }
            arr[j + gap] = temp;
        }
    }

    //选择排序

    //时间复杂度 O(N²)
    //最好情况，最坏情况都是O(N²)
    //不稳定
    //从i + 1 往后一边找最小的，往i处放
    public static void selectSort(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;

            for (int j = i + 1; j < arr.length; j++) {
                if(arr[minIndex] > arr[j]){
                    minIndex = j;
                }
            }
            swap(arr,i,minIndex);
        }
    }

    private  static void swap(int[] arr, int i ,int j ){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    //选择排序能不能从两边查找呢？
    public static void selectSort1(int[] arr){
        int left = 0;
        int right = arr.length - 1;

        while(left < right){
            int minIndex = left;
            int maxIndex = left;
            for (int i = left + 1; i <= right; i++) {
                if(arr[i] > arr[maxIndex]){
                    maxIndex = i;
                }
                if(arr[i] < arr[minIndex]){
                    minIndex = i;
                }
            }
            swap(arr,left,minIndex);
            //这里存在最大值下标，即 maxIndedx 刚好等于left
            //left 和 minIndex 对应的值交换之后，left 上的值就不是区间最大值了
            //所以 maxIndex 就得改成 minIndex
            if(left == maxIndex){
                maxIndex = minIndex;
            }
            swap(arr,right,maxIndex);
            left++;
            right--;
        }
    }

    //堆排序
    public static void heapSort(int[] arr){
        createHugeHeap(arr);
        int end = arr.length - 1;
        while(end > 0){
            swap(arr,0,end);
            shiftDown(arr,0, end);
            end--;
        }
    }

    private static void createHugeHeap(int[] arr){
        for (int parent = (arr.length - 1 - 1)/2; parent >= 0 ; parent--) {
            shiftDown(arr,parent,arr.length);
        }
    }

    private static void shiftDown(int[] arr,int parent, int len){
        int child = 2 * parent + 1;
        while(child < len){
            if(child + 1 < len && arr[child] < arr[child + 1] ){
                child++;
            }

            if(arr[child] > arr[parent]){
                swap(arr,child,parent);
                parent = child;
                child = 2 * parent + 1;
            }else{
                break;
            }

        }
    }

    public static void quickSort(int[] arr){
        quick(arr,0,arr.length - 1);
    }

    private static void quick(int[] arr,int start,int end){
        if(start >= end){
            return ;
        }

        //使用三数取中法对快排进行优化：
        int index = midThree(arr,start,end);
        swap(arr,start,index);

        int pivot = partition1(arr,start,end);
        //int pivot = partition2(arr ,start,end);
        quick(arr,start,pivot - 1);
        quick( arr,pivot + 1,end);
    }

    //填坑法
    private static int partition1(int[] array,int left,int right){
        int temp = array[left];
        while(left < right){
            while(left < right && array[right] >= temp ){
                right--;
            }
            array[left] = array[right];

            while(left < right && array[left] <= temp){
                left++;
            }
            array[right] = array[left];
        }
        array[left] = temp;
        return left;
    }

    //Hoare法
    private static int partition2(int[] array,int left,int right) {
        int temp = array[left];
        int i = left;
        //左边作为基准，为什么要先走右边？
        //先走右边，最后左右下标相遇的点，是比基准小的值，最后与基准交换
        //如果先走左边，最后比基准大的会换到左边，排序失败！
        while(left < right){
            while(left < right && array[right] >= temp){
                right--;
            }

            while(left < right && array[left] <= temp){
                left++;
            }

            swap(array,right,left);
        }
        swap(array,left,i);
        return left;
    }

    //快速排序存在问题：已经有序的数组，可能会造成单侧递归的现象，这样浪费空间，以及递归多次的情况，需要对快排进行优化
    //三数取中法
    private static int midThree(int[] arr,int left ,int right){
        int mid = (left + right)/2;
        int temp = 0;
        if(arr[right] > arr[left]){
            if(arr[mid] > arr[right]){
                return right;
            }else if(arr[mid] < arr[left]){
                return left;
            }else{
                return mid;
            }
        }else{
            if(arr[mid] > arr[left]){
                return left;
            }else if (arr[mid] < arr[right]){
                return right;
            }else{
                return mid;
            }
        }
    }

    //快排的非递归实现
    //其实依旧要用到 填坑法 或是 hoare法
    public static void quickSort1(int[] arr){
        int left = 0;
        int right = arr.length - 1;
        int pivot = partition1(arr,left,right);
        Deque<Integer> stack = new LinkedList<>();
        if(pivot - left > 1){
            stack.push(left);
            stack.push(pivot - 1);
        }
        if(right - pivot > 1){
            stack.push(pivot + 1);
            stack.push(right);
        }

        while(!stack.isEmpty()){
            right = stack.pop();
            left = stack.pop();
            pivot = partition1(arr,left,right);
            if(pivot - left > 1){
                stack.push(left);
                stack.push(pivot - 1);
            }
            if(right - pivot > 1){
                stack.push(pivot + 1);
                stack.push(right);
            }
        }
    }

    //归并排序_递归
    public static void mergeSort(int[] arr){
        mergeFunc(arr,0, arr.length - 1);
    }

    private static void mergeFunc(int[] arr,int left,int right){
        if(left >= right){
            return;
        }

        int mid = (left + right) / 2;
        mergeFunc(arr,left,mid);
        mergeFunc(arr,mid + 1,right);
        merge(arr,left,right,mid);
    }

    private static void merge(int[] arr , int start, int end,int mid){
        int s1 = start;
        int s2 = mid + 1;
        int[] temp = new int[end - start + 1];
        int k = 0;
        while(s1 <= mid  && s2 <= end ){
            if(arr[s1] < arr[s2]){
                temp[k] = arr[s1];
                k++;
                s1++;
                //等价于
                //temp[k++] = arr[s1++];
            }else{
                temp[k] = arr[s2];
                k++;
                s2++;
            }
        }
        while(s1 <= mid){
            temp[k++] = arr[s1++];
        }
        while(s2 <= end){
            temp[k++] = arr[s2++];
        }

        for (int i = 0; i < temp.length; i++) {
            arr[start + i] = temp[i];
        }
    }

    //归并排序——非递归
    //gap ：两个合并成一组的容量
    public static void mergeSort1(int[] arr){
        int gap = 1;
        while(gap < arr.length){
            for (int i = 0; i < arr.length; i+= gap * 2) {
                int start = i;
                //这里，end 和 mid 可能会越界
                //先确定 mid 再 确定 end 的坐标
                //mid 其实是前一次合并排序完成之后，合并数组的最后一个坐标
                int mid = start + gap - 1;
                if(mid >= arr.length){
                    mid = arr.length - 1;
                }
                int end = mid + gap;
                if(end >= arr.length){
                    end = arr.length - 1;
                }
                merge(arr,start,end,mid);
            }
            gap *= 2;
        }
    }





}
